package com.yang.Dp.bags;

/**
 * @Author: yang
 * @Description:
 * 给你一个整数数组 nums 和一个整数 target 。
 * 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
 *     例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
 * 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
 * @Date: Created in 17:25 2022/8/10
 * @Modified By:
 */
public class LeetCode494 {
}

class LeetCode494Solution {
    public int findTargetSumWays(int[] nums, int target) {
        // 本题的关键 确定一个点  那就是 假设 x为加的数 那么  sum-x 为减去的数  所以有 X =  S + (SUM - X); S为目标数
        // 那现在问题就转移为 要让 容量为X的背包 装满 有多少方法？

        int sum = 0;
        for(int num : nums){
            sum += num;
        }

        // 根据 target = left - right 与 sum = left + right 可以推出  left = (sum + target) / 2
        int bageSize = (sum + target) / 2;

        // 按照公式递推 X =  S + (SUM - X)  如果为奇数 那么 x就是小数 不满足条件
        if((sum + target) % 2 == 1){
            return 0;
        }
        if(Math.abs(target) > sum){
            return 0;
        }

        int dp[] = new int[bageSize + 1];
        // 装满0 有一种方法 即什么都不装
        dp[0] = 1;
        for(int i = 0; i < nums.length; i++){
            for(int j = bageSize; j >= nums[i]; j--){
                // 比如说 left = 5 时 如果已经拥有了一个nums[i] = 1 那么就还需要dp[4]种方法
                // 已经有一个2 nums[i] 的话，有 dp[3]种方法 凑成 dp[5]
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bageSize];
    }
}
